package day1_array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * @Author: yuisama
 * @Date: 2021/8/4 12:20
 * @Description:Num136_只出现一次的数字
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * 说明：
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 * 示例 1:
 * 输入: [2,2,1]
 * 输出: 1
 * 示例2:
 * 输入: [4,1,2,1,2]
 * 输出: 4
 * 链接：https://leetcode-cn.com/problems/single-number
 */
public class num136_singleNumber {
    // 空间复杂度O(n),引入哈希表
    public int singleNumber1(int[] nums) {
        int singleKey = 0;
        Map<Integer,Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!numMap.containsKey(i)) {
                numMap.put(i,1);
            }else {
                numMap.put(i,2);
            }
        }
        Iterator<Map.Entry<Integer, Integer>> iterator = numMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, Integer> next = iterator.next();
            if (next.getValue() == 1) {
                singleKey  = next.getKey();
                break;
            }
        }
        return singleKey;
    }

    /**
     * 空间复杂度O(1),异或运算
     * a⊕0=a。
     * a⊕a=0。
     */
    public int singleNumber(int[] nums) {
        int singleNum = 0;
        for(int i : nums) {
            singleNum ^= i;
        }
        return singleNum;
    }

    /**
     * 排序法
     * @param nums
     * @return
     */
    public int singleNumber2(int[] nums) {
        // 先将原数组排序
        Arrays.parallelSort(nums);
        int singleNum = 0;
        for (int i = 0; i < nums.length; i++) {
            // num[i]存在重复元素
            if (i == nums.length - 1) {
                singleNum = nums[i];
                break;
            }
            if (nums[i] == nums[i+1]) {
                i++;
            }else {
                singleNum  = nums[i];
                break;
            }
        }
        return singleNum;
    }
}
